import java.util.*;

class Node {
    private Object item;
    private Node left;
    private Node right;

    public Node(Object item) {
	this(item, null, null);
    }
    public Node(Object item, Node left, Node right) {
	this.item = item;
	this.left = left;
	this.right = right;
    }
    private void visit() {
	System.out.print(item + " ");
    }
    public void preorder() {
	visit();
	if (left != null)
	    left.preorder();
	if (right != null)
	    right.preorder();
    }
    public void postorder() {
	if (left != null)
	    left.postorder();
	if (right != null)
	    right.postorder();
	visit();
    }
    public void inorder() {
	if (left != null)
	    left.inorder();
	visit();
	if (right != null)
	    right.inorder();
    }

    public Iterator preIterator() {
	return new PreIterator();
    }
    public Iterator levelIterator() {
	return new LevelIterator();
    }
    private class PreIterator implements Iterator {
	private Stack stack;
	PreIterator() {
	    stack = new Stack();
	    if (Node.this != null)
		stack.push(Node.this);
	}
	public boolean hasNext() {
	    return !stack.empty();
	}
	public Object next() {
	    Node n = (Node)stack.pop();
	    if (n.right != null)
		stack.push(n.right);
	    if (n.left != null)
		stack.push(n.left);
	    return n.item;
	}
	public void remove() {
	    throw new UnsupportedOperationException();
	}
    }
    private class LevelIterator implements Iterator {
	private Queue queue;
	LevelIterator() {
	    queue = new ListQueue();
	    if (Node.this != null)
		queue.enqueue(Node.this);
	}
	public boolean hasNext() {
	    return !queue.isEmpty();
	}
	public Object next() {
	    Node n = (Node)queue.dequeue();
	    if (n.left != null)
		queue.enqueue(n.left);
	    if (n.right != null)
		queue.enqueue(n.right);
	    return n.item;
	}
	public void remove() {
	    throw new UnsupportedOperationException();
	}
    }
}

class TreeIter {
    public static Node makeTree() {
	return
	    new Node("*",
		     new Node("+", 
			      new Node("*",
				       new Node("2"),
				       new Node("4")
				       ),
			      new Node("/",
				       new Node("8"),
				       new Node("4")
				       )
			      ),
		     new Node("-",
			      new Node("2"),
			      new Node("4")
			      )
		     );
    }

    public static void print(Iterator iter) {
	while (iter.hasNext())
	    System.out.print(iter.next() + " ");
	System.out.println();
    }
    public static void main(String[] args) {
	Node tree = makeTree();
	System.out.println("PREorder");
	tree.preorder();
	System.out.println();
	System.out.println("POSTorder");
	tree.postorder();
	System.out.println();
	System.out.println("INorder");
	tree.inorder();
	System.out.println();
	System.out.println("PREorder");
	Iterator pre = tree.preIterator();
	print(pre);
	System.out.println("LEVEL-order");
	Iterator level = tree.levelIterator();
	print(level);
    }
}